import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Stack;
import java.util.TreeMap;


public class Ex5_2 {


	public Ex5_2() {}

	public static void main(String[] args) {

		Ex5_2 exe = new Ex5_2();
		//TreeMap<String,ArrayList<String>> reads = 
		//		exe.getReads("C:\\Users\\josemfer\\Downloads\\dataset_57_6.txt");
		
		ArrayList<String> combs = exe.generateCombinations(17);
		TreeMap<String,ArrayList<String>> reads = exe.generateGraphOut(combs);
		
		//Start with an empty stack and an empty circuit (eulerian path).
		// If all vertices have same out-degrees as in-degrees - choose any of them.
		// If all but 2 vertices have same out-degree as in-degree, and one of those 2 vertices has out-degree 
		//    with one greater than its in-degree, and the other has in-degree with one greater than its out-degree - 
		//    then choose the vertex that has its out-degree with one greater than its in-degree.
		//2. If current vertex has no out-going edges (i.e. neighbors) - add it to circuit, remove the last vertex from the stack and set it as the current one.
		//Otherwise (in case it has out-going edges, i.e. neighbors) - add the vertex to the stack, 
		//take any of its neighbors, remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
		//3. Repeat step 2 until the current vertex has no more out-going edges (neighbors) and the stack is empty.
	
		
		ArrayList<String> eulerPath = new ArrayList<String>();
		Stack<String> stack = new Stack<String>();		
		//String current = exe.selectStartNode(reads);
		String current = "0000000000000000";
		
		ArrayList<String> outgoings = reads.get(current);
		
		do {								
			//remove the last vertex from the stack and set it as the current one
			if (outgoings == null || outgoings.size() == 0) {			
				eulerPath.add(current);
				current = stack.pop();
			} else { 
				// add the vertex to the stack
				stack.push(current);
				//take any of its neighbors
				String outgoing = outgoings.get(0);
				// remove the edge between that vertex and selected neighbor
				if (outgoings.size() == 1) {
					reads.remove(current);
				} else {
					outgoings.remove(0);
				}
				//set that neighbor as the current vertex
				current = outgoing;			
			}	
			outgoings = reads.get(current);			
		} while(!stack.isEmpty() ||  outgoings != null);
		
		eulerPath.add(current);
		Collections.reverse(eulerPath);

		//String prevNode = null;
		//ArrayList<String> seq = new ArrayList<String>();
		String chain = "";
		for (String node : eulerPath) {
			//System.out.print(node.substring(0,1));
			chain += node.substring(0,1);
		}
		
		exe.writeFile(chain);
		
		/*int h = chain.length()-1;
		chain = chain + chain;
		System.out.println("");
		for (int i=0;i<h;i++) {
			System.out.println( chain.substring(i,i+4));
		}*/
		
		
		
	}

	
	private void writeFile(String text) {
		Writer writer = null;

		try {
		    writer = new BufferedWriter(new OutputStreamWriter(
		          new FileOutputStream("C:\\Users\\josemfer\\Downloads\\ex5_3_out.txt"), "utf-8"));
		    writer.write(text);
		} catch (IOException ex) {
		  // report
		} finally {
		   try {writer.close();} catch (Exception ex) {}
		}
	}
	

	private String selectStartNode(TreeMap<String,ArrayList<String>> reads) {
		
		HashMap<String,Integer> inDegrees = new HashMap<String,Integer>();
		
		for (Entry<String,ArrayList<String>> read : reads.entrySet()) {			
			ArrayList<String> outgoings = (ArrayList<String>) read.getValue();
			for (String outgoing : outgoings) {
				if (inDegrees.containsKey(outgoing)) {
					Integer actualDegree = inDegrees.get(outgoing);
					 inDegrees.put(outgoing, actualDegree + 1);					
				} else {
					 inDegrees.put(outgoing, 1);		
				}
			}
		}
		
		for (Entry<String,ArrayList<String>> read : reads.entrySet()) {			
			String origin = read.getKey();
			ArrayList<String> outgoings = read.getValue();
			Integer inDegree = inDegrees.get(origin);
			if (inDegree == null) {
				inDegree = 0;
			}
			Integer outDegree = outgoings.size();
			if (outDegree == inDegree + 1) {
				return origin;
			}			
		}	
		
		return null;
	}
	
	private TreeMap<String,ArrayList<String>> getReads(String file) {		
		TreeMap<String,ArrayList<String>> reads = new TreeMap<String,ArrayList<String>>();	
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;		
			while ((line = br.readLine()) != null) {
				line = line.trim();
				String[] split = line.split("->");
				String origin = split[0].trim();
				String dest = split[1].trim();
				ArrayList<String> outgoings = reads.get(origin);
				if (outgoings == null) {
					outgoings = new ArrayList<String>();
					outgoings.add(dest);
					reads.put(origin, outgoings);
				} else {					
					if (!outgoings.contains(dest)) {
						outgoings.add(dest);
					}
				}				
			}			
			br.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return reads;
	}

	private TreeMap<String,ArrayList<String>> 
								generateGraphOut(ArrayList<String> kmers) {
		TreeMap<String,ArrayList<String>> graph = 
				new TreeMap<String,ArrayList<String>> ();  
		for (String kmer : kmers) {
			String prefix = kmer.substring(0,kmer.length()-1);
			String sufix = kmer.substring(1,kmer.length());
			ArrayList<String> outgoings = graph.get(prefix);
			if (outgoings == null) {
				outgoings = new ArrayList<String>();
				outgoings.add(sufix);
				graph.put(prefix, outgoings);
			} else {
				if (!outgoings.contains(sufix)) {
					outgoings.add(sufix);
				}
			}

		}
		return graph;
	}


	private ArrayList<String> generateCombinations(Integer k) {
		char[] symbols = {'0','1'};
		Integer m = symbols.length;
		ArrayList<String> list = new ArrayList<String>();
		for (int i=1;i<= Math.pow(m, k);i++) {
			String kmer = "";
			for (int j=0;j<k;j++) {
				Integer n = (i /  
						Double.valueOf(Math.pow(m, j)).intValue()) % m;
				kmer = kmer + symbols[n];
			}
			list.add(kmer);
		}		

		return list;
	}

	
	
	
}
